#include <stdio.h>
#include <stdlib.h>
//课时15作业
typedef int KeyType;
typedef struct BSTNode{
    KeyType key;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BiTree;

int BTSInsertRecursion(BiTree &T,KeyType k)
{
    if(T==NULL)
    {
        T= (BiTree)calloc(1,sizeof(BSTNode));
        T->key=k;
        return 1;
    }
    else if(k<T->key)
        return BTSInsertRecursion(T->lchild,k);
    else if(k>T->key)
        return BTSInsertRecursion(T->rchild,k);
    else
        return 0;
}
void CreateBST(BiTree &T,KeyType* str,int len)
{
    for (int i = 0; i < len; ++i) {
        BTSInsertRecursion(T,str[i]); //把某一结点放入二叉查找树
    }
}
void InOrder(BiTree T,KeyType *array)
{
    static int i=0;  //静态局部变量，只会初始化一次和全局变量类似，只在函数内有效
    if(T!=NULL)
    {
        InOrder(T->lchild,array);
        printf("%3d",T->key);
        array[i]=T->key;
        i+=1;
        InOrder(T->rchild,array);
    }
}
int BinarySearch(KeyType *array,KeyType key,int len)
{
    int low=0,high=len-1,mid;
    while (low<=high)
    {
        mid=(low+high)/2;
        if(key<array[mid])
        {
            high=mid-1;
        } else if(key>array[mid])
        {
            low=mid+1;
        } else{
            return mid;
        }
    }
    return -1;
}
int main() {
    BiTree T=NULL; //给树初始化为null
    KeyType str[10];
    int len=10;
    for (int i = 0; i < len; ++i) {
        scanf("%d",&str[i]);
    }
    CreateBST(T,str,len);
    InOrder(T,str);
    printf("\n");
    int pos=BinarySearch(str,21,len);
    if(pos)
    {
        printf("%d",pos);
    }
    return 0;
}
